package com.sjf.day04.kmp;

import java.util.Arrays;

/**
 * KMP算法
 *
 * @author <huangtang>
 * @since 2022/1/18 11:34
 **/
public class KMPAlgorithm {

    public static void main ( String[] args ) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

        int[] next = kmpMatch ("ABCDABD");
        System.out.println (Arrays.toString (next));

        int index = kmpSearch (str1 , str2 , next);
        System.out.println ("index =" + index);
    }

    /**
     * kmp搜索算法
     *
     * @param str1 父字符串
     * @param str2 子字符串
     * @param next 部分匹配数组
     * @return 如果是-1，则表示没有匹配到，否则返回第一个匹配字符的下标
     */
    public static int kmpSearch ( String str1 , String str2 , int[] next ) {
        //遍历父串
        for ( int i = 0, j = 0 ; i < str1.length () ; i++ ) {

            //需要考虑str1.charAt(i)!=str2.charAt(j)的情况,调整j的大小
            while (j > 0 && str1.charAt (i) != str2.charAt (j)) {
                j = next[j - 1];
            }

            if ( str1.charAt (i) == str2.charAt (j) ) {
                j++;
            }
            if ( j == str2.length () ) {
                return i - j + 1;
            }
        }
        return -1;
    }

    //获取到一个字符串(子串)的部分匹配值
    public static int[] kmpMatch ( String dest ) {
        //创建一个next数组保存部分匹配值
        int[] next = new int[dest.length ()];
        next[0] = 0;//如果字符串长度为0，部分匹配中就为0
        for ( int i = 1, j = 0 ; i < dest.length () ; i++ ) {
            while (j > 0 && dest.charAt (i) != dest.charAt (j)) {
                j = next[j - 1];
            }

            if ( dest.charAt (i) == dest.charAt (j) ) {
                //此时部分匹配值+1
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
